import collections


class Solution:
    def countOfAtoms(self, formula: str):
        st = [collections.defaultdict(int)]
        state = 0
        left = 0
        for index, c in enumerate(formula):
            if state == 0:
                if c == '(':
                    st.append(collections.defaultdict(int))
                if '0' <= c <= '9':
                    left = index
                    state = 1
                if 'A' <= c <= 'Z':
                    left = index
                    state = 2
            else:
                if state == 1:
                    if c == '(':
                        num = int(formula[left:index])
                        node = st.pop()
                        for key in node:
                            st[-1][key] += node[key] * num
                        left = index
                        st.append(collections.defaultdict(int))
                        state = 0
                    if '0' <= c <= '9':
                        continue
                    if 'A' <= c <= 'Z':
                        print(index)
                        num = int(formula[left:index])
                        node = st.pop()
                        for key in node:
                            st[-1][key] += node[key] * num
                        left = index
                        state = 2
                    if c == ')':
                        num = int(formula[left:index])
                        node = st.pop()
                        for key in node:
                            st[-1][key] += node[key] * num
                        left = index
                        state = 0
                else:
                    if state == 2:
                        if c == '(':
                            val = formula[left:index]
                            st[-1][val] += 1
                            left = index
                            state = 0
                            st.append(collections.defaultdict(int))
                        if 'a' <= c <= 'z':
                            continue
                        if c == ')':
                            val = formula[left:index]
                            st[-1][val] += 1
                            left = index
                            state = 0
                        if '0' <= c <= '9':
                            state = 3
                            last = formula[left:index]
                            left = index
                        if 'A' <= c <= 'Z':
                            last = formula[left:index]
                            left = index
                            st[-1][last] += 1
                    else:
                        if state == 3:
                            if c == '(':
                                num = int(formula[left:index])
                                st[-1][last] += num
                                st.append(collections.defaultdict(int))
                                left = index
                                state = 0
                            if 'A' <= c <= 'Z':
                                num = int(formula[left:index])
                                st[-1][last] += num
                                left = index
                                state = 2
                            if '0' <= c <= '9':
                                continue
                            if c == ')':
                                num = int(formula[left:index])
                                st[-1][last] += num
                                left = index
                                state = 0
        if state == 2:
            st[-1][formula[left:]] += 1
        if state == 1:
            num = int(formula[left:])
            node = st.pop()
            for key in node:
                st[-1][key] += node[key] * num
        if state == 3:
            num = int(formula[left:])
            st[-1][last] += num
        ans = collections.defaultdict(int)
        for node in st:
            for key in node:
                ans[key] += node[key]
        out = [[key, ans[key]] for key in ans]
        out.sort()
        new_out = []
        for a, b in out:
            if b > 1:
                new_out.append(a + str(b))
            else:
                new_out.append(a)
        return ''.join(new_out)


data = Solution()
# formula = "H2O"
# print(data.countOfAtoms(formula))
# formula = "Mg(OH)2"
# print(data.countOfAtoms(formula))
# formula = "K4(ON(SO3)2)2"
# print(data.countOfAtoms(formula))
formula = "((N42)24(OB40Li30CHe3O48LiNN26)33(C12Li48N30H13HBe31)21(BHN30Li26BCBe47N40)15(H5)16)14"
print(data.countOfAtoms(formula))